package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;
import cn.initcap.algorithm.graph.SparseGraph;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 图的广度优先遍历实现
 *
 * @author initcap
 * @date Created in 7/31/19 9:54 AM.
 */
public class GraphBfs {

    private Graph<Integer, Double> graph;
    private boolean[] visited;
    private List<Integer> order;

    public GraphBfs(Graph graph) {
        this.graph = graph;
        visited = new boolean[graph.nodeSize()];
        order = new ArrayList<>(graph.nodeSize());
        for (int i = 0; i < graph.nodeSize(); i++) {
            if (!visited[i]) {
                bfs(i);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new SparseGraph("algorithm/testG10.txt", false);
        GraphBfs bfs = new GraphBfs(graph);
        System.out.println("BFS ORDER ： " + bfs.order());
    }

    private void bfs(int s) {
        Queue<Integer> queue = new LinkedList();
        queue.add(s);
        visited[s] = true;
        while (!queue.isEmpty()) {
            int v = queue.poll();
            order.add(v);

            for (int w : graph.adj(v)) {
                if (!visited[w]) {
                    queue.add(w);
                    visited[w] = true;
                }
            }

        }
    }

    public Iterable<Integer> order() {
        return order;
    }

}
